package com.二叉树;
import java.util.*;

class Solution2{

    //前序遍历
    //时间复杂度：O(n)
    //空间复杂度：为递归过程中栈的开销，平均情况下为 O(log n)，最坏情况下树呈现链状，为 O(n)。
    public List<Integer> preOrder(TreeNode root){
        //用在存储遍历的结果
        ArrayList<Integer> res = new ArrayList<>();
        //判空
        if(root==null)
            return res;
        //存放当前节点
        TreeNode node=root;
        //定义一个栈
        Deque<TreeNode> stack = new LinkedList<>();
        //开始前序迭代遍历
        while(!stack.isEmpty() || node!=null){
            while(node!=null){
                //遍历该节点
                res.add(node.val);
                //挂起当前节点，放入栈中
                stack.push(node);
                //指向当前节点的左节点
                node=node.left;
            }
            node=stack.pop();
            node=node.right;
        }
        return res;
    }
    //中序遍历
    public List<Integer> inOrder(TreeNode root){
        //用在存储遍历的结果
        ArrayList<Integer> res = new ArrayList<>();
        //判空
        if(root==null)
            return res;
        //存放当前节点
        TreeNode node=root;
        //定义一个栈
        Deque<TreeNode> stack = new LinkedList<>();
        //开始迭代遍历
        while(!stack.isEmpty() || node!=null){
            while(node!=null){
                //挂起当前节点，放入栈中
                stack.push(node);
                //指向当前节点的左节点
                node=node.left;
            }
            node=stack.pop();
            //遍历该节点
            res.add(node.val);
            node=node.right;
        }
        return res;
    }
    //后序遍历-记录最后一次输出节点
    public List<Integer> postOrder(TreeNode root){
        //用在存储遍历的结果
        ArrayList<Integer> res = new ArrayList<>();
        //判空
        if(root==null)
            return res;
        //存放当前节点
        TreeNode curRoot=root;
        //存放最后一次遍历的节点
        TreeNode lastNode=null;
        //定义一个栈
        Deque<TreeNode> stack = new LinkedList<>();
        //开始迭代遍历
        while(!stack.isEmpty() || curRoot!=null){
            //循环将左节点入栈
            while(curRoot!=null){
                //挂起当前节点，放入栈中
                stack.push(curRoot);
                //指向当前节点的左节点
                curRoot=curRoot.left;
            }
            curRoot=stack.pop();
            //判断根节点是否满足遍历条件,只有当根节点的右节点为空，或者右节点已经输出过了才可以输出根节点
            if(curRoot.right==null || curRoot.right==lastNode){
                res.add(curRoot.val);
                lastNode=curRoot;
                curRoot=null;
            }else{
                stack.push(curRoot);
                curRoot=curRoot.right;
            }
        }
        return res;
    }
    //层次遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        //用于存放结果
        List<List<Integer>> ret = new ArrayList<>();
        if(root==null){
            return ret;
        }
        //定义一个队列
        Deque<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            //定义列表存放每一层元素
            List<Integer> level = new ArrayList<>();
            //记录每一层的节点个数
            int currentLevelSize=queue.size();
            for(int i=1;i<=currentLevelSize;i++){
                //出队
                TreeNode node=queue.poll();
                level.add(node.val);
                //将其左右节点添加进队列
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            //将该层结果添加到ret中
            ret.add(level);
        }
        return ret;
    }
    //剑指 Offer 32 - III. 从上到下打印二叉树 III
    public List<List<Integer>> levelOrder2(TreeNode root) {

        /*
        方法一：
            1.利用双端队列两头都可以添加元素的特性，添加元素到列表中
                LinkedList<Integer> level = new LinkedList<>();
            2.加入列表前，判断是奇数层，还是偶数层
                奇数层，从尾部添加
                偶数层，从头部添加
         */
        //用于存放结果
//        List<List<Integer>> ret = new ArrayList<>();
//        if(root==null){
//            return ret;
//        }
//        //定义一个队列
//        Deque<TreeNode> queue = new ArrayDeque<TreeNode>();
//        queue.offer(root);
//        while(!queue.isEmpty()){
//            //利用双端队列两头都可以添加元素的特性，添加元素到列表中
//            LinkedList<Integer> level = new LinkedList<>();
//            //记录每一层的节点个数
//            int currentLevelSize=queue.size();
//            for(int i=1;i<=currentLevelSize;i++){
//                //出队
//                TreeNode node=queue.poll();
//                if(ret.size()%2==0) level.addLast(node.val);//奇数层，从尾部添加
//                else level.addFirst(node.val);//偶数层，从头部添加
//                //将其左右节点添加进队列
//                if(node.left!=null){
//                    queue.offer(node.left);
//                }
//                if(node.right!=null){
//                    queue.offer(node.right);
//                }
//            }
//            //将该层结果添加到ret中
//            ret.add(level);
//        }


        /*
        方法二：
        思路：1.消除判断奇偶层的冗余，将奇数层节点的打印和子节点的入列逻辑分离
                1.1如果是奇数层节点，从左向右打印节点(左为头，右为尾)，并从左向右添加其子节点
                1.2如果是偶数层节点，从右向左打印节点，并从右向左添加其子节点
         */
        List<List<Integer>> ret = new ArrayList<>();
        if(root==null){
            return ret;
        }
        //定义一个队列
        Deque<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.addLast(root);
        while(!queue.isEmpty()){
            List<Integer> level = new ArrayList<>();
            //从左向右打印奇数层节点
            int currentSize=queue.size();
            for (int i = 0; i < currentSize; i++) {
                TreeNode node=queue.removeFirst();
                level.add(node.val);
                //从左向右添加子节点
                if(node.left!=null) queue.addLast(node.left);
                if(node.right!=null) queue.addLast(node.right);
            }
            ret.add(level);
            //如果队列已经为空，提前退出循环
            if(queue.isEmpty()) return ret;
            //从右向左打印偶数层节点
            List<Integer> level2 = new ArrayList<>();
            currentSize=queue.size();
            for (int i = 0; i < currentSize; i++) {
                TreeNode node=queue.removeLast();
                level2.add(node.val);
                //从右向左打印子节点
                if(node.right!=null) queue.addFirst(node.right);
                if(node.left!=null) queue.addFirst(node.left);
            }
            ret.add(level2);
        }
        return ret;
    }

}

public class 迭代遍历 {
    public static void main(String[] args) {

    }
}
